Primakov giữ chức Bộ trưởng ngoại giao từ tháng 1 năm 1996 đến tháng 9 năm 1998. Trên cương vị này, ông đã giành được sự tôn trọng cả trong nước và danh tiếng như một người cứng rắn cương quyết ở nước ngoài[5] một người ủng hộ mạnh mẽ và thực tế cho những lợi ích của Nga, và một người phản đối sự mở rộng của NATO tới các nước thuộc khối Đông Âu cũ, dù vào ngày 27 tháng 5 năm 1997, sau 5 tháng đàm phán với Tổng thư ký NATO Javier Solana, Nga đã ký Luật Nền tảng, được coi là đánh dấu sự chấm dứt của những sự thù địch của thời Chiến tranh Lạnh.

Ông cũng nổi tiếng là một người ủng hộ Chủ nghĩa đa cực như một sự thay thế cho sự độc quyền chính trị toàn cầu của Hoa Kỳ sau sự sụp đổ của Liên xô và cuộc Chiến tranh Lạnh. Primakov đã kêu gọi một chính sách đối ngoại của Nga dựa trên sự hoà giải với chi phí thấp trong khi mở rộng ảnh hưởng tới Trung Đông và các nước cộng hoà thuộc Liên xô cũ. Chính sách này, được gọi là "học thuyết Primakov", đã hoàn toàn thất bại[6]. Một quan điểm khác là dù phong cách của Primakov là chống phương Tây, thực tế ông chiều theo các ý muốn phương Tây.[7]. Primakov đã coi Nga, Trung Quốc, và Ấn Độ như là một "tam giác chiến lược" để cân bằng với Hoa Kỳ. Động thái được diễn giải bởi một số nhà quan sát như một sự đồng ý cùng chiến đấu chống lại 'các cuộc các mạng màu' ở Trung Á[8] Samuel Huntington đã gọi nó là một liên minh chống bá chủ trong một tiểu luận có tiêu đề 'Siêu cường cô độc' Lưu trữ 2006-09-18 tại Wayback Machine.